The Data Encryption Standard public key encryption algorithm (“DES”) is a symmetric-key encryption developed in 1975 and standardized by the American National Standards Institute (“ANSI”) in 1981 as the ANSI X.3.9.2 standard. DES utilizes a single key to encrypt and decrypt a message. Additional information regarding the DES algorithm can be found in the Handbook of Applied Cryptography by Menezes, Oorschot, and Vanstone, CRC Press, 1997.
As shown in FIG. 1, the DES algorithm takes as input a 64-bit text message. It also takes as input a 64-bit key (not shown). However, only 56 of the 64 bits are utilized. From these 56 bits, 16 48-bit sub-keys are created. The first step in encrypting a 64-bit message, as shown in Block 101 of FIG. 1, is to permutate the 64-bit input message. While software implementations of the DES algorithm require significant time to perform this permutation, hardware implementations of the DES algorithm can perform this permutation by appropriately routing signals so that no transistors are required and no significant delay occurs.
Referring again to FIG. 1, the result of the input permutation is divided into two 32-bit halves. The lower 32 bits will be referred to as the Right Half 0. The upper 32 bits will be referred to as the Left Half 0.
The Right Half 0 and sub-key 1 are input into “function” logic block 102. The “function” logic block 102 will be discussed more fully below. The output of “function” logic block 102 and the Left Half 0 are input into an exclusive-or operator 103. The exclusive-or operator is represented with a circle around a “+” symbol. As shown in FIG. 1, the processing of the Right Half 0 and the Left Half 0 by “function” block 102 and the exclusive-or operator 103 will be referred to as Round 1.
After the completion of Round 1, the output of the exclusive-or operator 103, which will be referred to as Right Half 1, and sub-key 2 are input into “function” logic block 104. The output of “function” logic block 104 and Right Half 0, which will also be referred to as Left Half 1, are input into exclusive-or operator 105. The processing of the Right Half 1 and the Left Half 1 by “function” block 104 and the exclusive-or operator 105 will be referred to as Round 2.
As shown in FIG. 1, Round 3 and Rounds 4 through 15 are identical to Round 2.
Round 16 includes inputting the Right Half 15 and sub-key 16 into “function” logic block 106. The output of “function” logic block 106 and Left Half 15, are input into exclusive-or operator 107.
After the completion of Round 16, the Right Half 16 and the Left Half 16 are combined to form a 64-bit number. The 64-bit number is then permutated by output permutation block 108. The permutation performed by output permutation block 108 is the inverse of the permutation performed by input permutation block 101. The result of the output permutation block 108 is 64 DES encrypted bits.
As discussed above, FIG. 1 includes 16 “function” logic blocks (four of which are shown). FIG. 2 presents a diagram of a “function” logic block. As shown in block 201 of FIG. 2, the 32-bit input to the “function” block is expanded to 48 bits by duplicating half of the 32 bits. In software implementations of the DES algorithm, this expansion takes a significant amount of time. However, in hardware implementations of the DES algorithm, the expansion can be performed by appropriately routing signals so that no transistors are required and no significant delay occurs. Next, the expanded 48 bits and a sub-key are input into exclusive-or operator 202. The result of the exclusive-or operation is split into eight groups. Each of these groups contains 6 bits. Each group of 6 bits is then input into one of eight S boxes 203-210. The S boxes perform table look-ups and output eight groups of 4 bits. For example, if the value of the 6 bit input group is k, then the S box would output the kth 4 bit entry in the S box's table. Each S box utilizes a different table. Typically, S boxes are implemented utilizing high-speed random access memory (“RAM”). The eight 4-bit outputs of the S boxes are then combined and permutated as shown in Block 211 of FIG. 2. In software implementations of the DES algorithm, the permutation takes a significant amount of time. However, in hardware implementations of the DES algorithm, the permutation can be performed by appropriately routing signals so that no transistors are required and no significant delay occurs.
FIG. 3 presents a simplified version of rounds 2 and 3 of a conventional hardware implementation of the DES algorithm. Because permutations and expansions can be performed by routing signals without the use of transistors, and hence do not impact the speed of execution of a hardware implementation of the DES algorithm, the permutations and expansions are not shown in FIG. 3. As is evident from FIG. 3, the critical path between S boxes 301 and S boxes 304 includes two exclusive-or operators 302 and 303.
As modern computers need to encrypt and decrypt large amounts of data using the DES algorithm, a need exists to increase the speed of hardware executed DES algorithms. Thus, there is a need to shorten the critical path between S boxes in hardware implementations of the DES algorithm.